\documentclass{article}[11pt]
\usepackage{amsmath}
\author{Jiajin Yu}
\title{Report of The Survey of "Lights Out!"}
\begin{document}
\newcommand{\allone}{\emph{All-Ones Problem}}
\newcommand{\minallone}{\emph{Minimum All-Ones Problem}}
\newcommand{\splus}{$\sigma^{+}$-game}
\maketitle
\section{Problem Definition}
The combinatorics game "Lights out!" is played on an $m \times n$ chessboard
where each cell equips with an indicator light and button. If the button of a
square is pressed, the light of that square will change from off to on and vice versa; the same happens to lights of all the edge-adjacent squares. Initially
all lights are on. Now, consider the following question: is it possible to
press a sequence of buttons in such a way that in the end all lights are off? We will refer to this problem as the \allone. If there are solutions, how to find buttons to press as few as possible? We refer this as the \minallone. We have to emphasize that when these two problems are referred, the initial condition of the chessboard is all off and the graph is a general undirected graph, not a grid. If the underlying graph is a grid and initial condition and end result are not specified, we will call it a \splus.
\section{Approaches}
\subsection{Graph-theoretic}
I found graph-theoretic proof of \allone{} based on induction. There are results of the \minallone{} for tree, unicyclic and bicyclic graphs by using graph-theoretic technique. Although there are lots of paper devoted to the perfect domination and $d$-covers, I do not see the connection between those and "Lights out!".  
\subsection{Cellular Automata}
The first result of the \allone{} is obtained by K.Sunter using cellular
automata. After that he also have several paper devoted to the topic "Additive
Cellular Automata", which include an NPC proof of the \minallone. (I got the NPC proof from the author). Although cellular automata is the framework he used, the proof technique underneath(except NPC proof) is linear algebra basically.
\subsection{Linear algebra}
Linear algebra over $GF(2)$ is the most widely used approach to solve the
problem. Here is the basic equation:
\begin{equation}\label{basic}
    (A+I)X = Y
\end{equation}
In \ref{basic}, $A$ is the adjacent matrix for the graph. $I$ means a vertex is adjacent to itself. $X$ is the activation steps and $Y$ is the original setting. For an example, if all of buttons are \texttt{ON} initially, then $Y=(1, 1, \ldots, 1)$. In order to decide the solvability of game, the nullspace and rangesapce of $A$ has to be studied. Fibonacci polynomial defined over $GF(2)$ by \[f_n = xf_{n-1} + f_{n-2} \quad n \geq 2, f_0 = 0, f_1 = 1\] is the basic tool to study the two spaces of $A$ for \emph{grid graph}. Coding theory are also used to solve some optimization problems for general graph.
\section{Known results}
The very first result of this problem is that all on can always be turned to all off for any graph no matter the neighborhood is closed or not. This result is obtained both from graph theory and linear algebra. Finding the minimum steps to turn to all off from all on is proved to be NPC. Only cases for trees and unicyclic and bicyclic graphs are solved by graph theory. All the other results are obtained by using linear algebra, Fibonacci polynomials over $GF(2)$ and coding theory together. List a fraction of them following.
\begin{itemize}
    \item Is a $m\times n$ grid graph completely solvable(i.e. any initial configuration can be turned to all off)?
    \item Deciding whether a graph $G$ can be transformed with at least $k$ switch off(i.e. with some initial configuration, can we find the maximize number of the off switch) is NPC.
    \item For a constant $c$, we can determine in polynomial time whether every starting configuration can be reduced with at most $c$ lights on.
\end{itemize}
 \section{A rough idea of the thesis}
 Since most deep results are obtained by linear algebra and Fibonacci polynomials. They should be the main framework in thesis. Graph theory should be touched when necessary. In the thesis, first introduce the problem and use both graph theory and linear algebra to prove \allone. After the basic part, use linear algebra and Fibonacci polynomials to develop the remaining results.
\end{document}
